package Z.dailyExercise._0106;

import java.util.ArrayList;

public class _28_实现strStr {

    /**
     * 自解：双指针 i指向haystack j指向needle
     * 如果needle为空
     *
     * i从0开始遍历 遇到【i】=【j】 index = i判断【i+1】=？【j+1】
     * 如果相等 i++ j++
     * 如果不相等 j不动 i依然后移
     *
     * 以上两线操作时 如果j先走完 那就返回index
     * 如果i先走完 那就返回-1
     * ==错误 如果存在needle中多了几个字符
     * 如果中途不匹配 j重新
     * ==错误 没有解决 mississipi 和 issip问题
     * --两次遍历先找到第一个字符所在的haysytack
     *
     * ==太慢了 10% 10%
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {

        if (needle.length() == 0){
            return 0;
        }
        if(haystack.length() == 0){
            return -1;
        }


        int j=0;
        boolean start= false;//表示是否已经开始匹配
        int index =0;
        ArrayList<Integer> list = new ArrayList<>();//存第一个匹配的索引字符
        for (int i=0;i<haystack.length();i++){
            if (haystack.charAt(i)==needle.charAt(0)){
                list.add(i);
            }
        }
        for (int i=0;i<list.size()  ; i++){
            index = list.get(i);

            while (index < haystack.length() && j<needle.length()
                    && haystack.charAt(index)==needle.charAt(j)){
                j++;
                index++;
            }
            //是不相等退出 还是两个指针走完了
            if (j == needle.length()){
                return list.get(i);
            }
            if (index== haystack.length()){
                return -1;
            }
            //本次不匹配 j归零
            j = 0;
        }

        return -1;



    }
}
